\section{Expanders}
\label{sec:exp}

For expander graphs, we  prove a high probability cover
time  of $O(\log^2 n)$. The proof is broken up into two phases. 
In the first phase we show that a cobra walk starting from any
vertex will reach a constant fraction of the vertices in logarithmic (in $|V|$) time
w.h.p. In the second phase, we create a process which stochastically
dominates the cobra walk and show that this new process will cover
the entire rest of the graph again in polylogarithmic time w.h.p.

The main result of this section can be stated formally as follows:

\begin{theorem} 
\label{expander-result}
Let $G$ be any $d$-regular $\epsilon$-expander with $\epsilon, \delta$
not depending on $n$ (the number of vertices in $G$), with $\delta <
\frac{1}{2}$, and $\epsilon$, a sufficiently small constant such
that
\begin{equation}
\label{expansionconstraint}
\frac{1}{\epsilon^2 (1 - \delta) + \delta} >  \frac{d( d e^{-k} + (k-1)) - \frac{k^2}{2}}{d(e^{-k} + (k-1)) - \frac{k^2}{2}} . \\
\end{equation}
Then w.h.p. a cobra walk with branching 
factor $k=2$ and starting from any vertex in $G$ will cover $G$ in $O(\log^2 n)$ time.
\end{theorem} 

Recall that $d$-regular $\eps$-expanders are defined in
Definition~\ref{def:exp}, and Theorem~\ref{thm:tanner} places a lower
bound on the size of neighborhoods in such an expander.

We also note that the condition in the above theorem is satisfied if
$\epsilon$ is sufficiently small for a fixed $k$. However, $k$ can also be
viewed as an adjustable parameter. Increasing $k$ would allow for graphs 
with worse expansion to be covered by this result. 

In the case where $k = 2$, the above condition holds for strong expanders,
such as the Ramanujan graphs, which have $\epsilon \leq
2\sqrt{d-1}/d$, and random $d$-regular graphs, for $d$ sufficiently
large.

As described above, the proof of Theorem~\ref{expander-result} has two parts. The first part, Phase I, handles
the behavior of the cobra walk on $G$ in the period between its start at a single vertex in $G$ and the time when
there are a linear number of active vertices (i.e. a constant fraction of the vertices). 
We show that this phase lasts no longer than $O(\log n)$ time.

The second part, Phase II, shows that once the cobra walk has reached a state in which a large fraction of
vertices are active, the rest of the vertices will be hit by the walk within at most $O(\log^2 n)$ rounds. The method of 
showing this is somewhat indirect, in that the bound is shown for a somewhat similar process that stochastically
dominates a cobra walk. The main idea, however, is that any vertex in $G$ will be hit by the cobra walk
within $O(\log n)$ time with constant probability. Thus, after $\Theta(\log n)$ runs of $O(\log n)$ steps, any (single)
vertex will be hit with high probability. Performing a union bound over all vertices and choosing constants appropriately
achieves the $O(\log^2 n)$ bound for the whole graph. 


We next state the two lemmas associated with Phase I and Phase 2, respectively. Combining these two lemmas proves 
Theorem~\ref{expander-result} 

\begin{lemma}
\label{exp:phaseI}
Let $G$ be any $d$-regular $\epsilon$-expander with $\epsilon, \delta$
not depending on $n$ (number of vertices in $G$), with $\delta <
\frac{1}{2}$, and $\epsilon$ satisfying~\ref{expansionconstraint}.
Then in time $O(\log n)$, w.h.p. a cobra walk on $G$ with branching
factor $k$, will attain an active set of
size $\delta n$.
\end{lemma}


\begin{lemma}
\label{exp:phaseII}
Let $G$ be as above, and let $W$ be a cobra walk on $G$ that at time
$T$ has reached an active set of size $\delta n$. Then w.h.p in an
additional $O(\log^2 n)$ steps every vertex of $G$ will have been visited
by $W$ at least once.
\end{lemma}   

\subsection{Phase 1} 

To prove Lemma~\ref{exp:phaseI} we prove that active sets up to a
constant fraction of $V$ are growing at each step by a factor greater
than one. To do this we show first that the size of the active set is
growing by an exponential factor in expectation
(c.f. Lemma~\ref{exp:expect}).  We then use a standard martingale
argument to show that this growth occors in any single step with high
probability (c.f. Lemma~\ref{exp:martingale}).  Finally to complete
the proof of Lemma~\ref{exp:phaseI} we show that there are a sufficient
number of growth steps within the first $O(\log n)$ rounds. To do this
we view the size of the active set itself as a random variable and
show that it is dominated by a random process derived from a negative
binomial random variable which itself satisfies the $O(\log n)$ bound.

\onlyShort{The proof can be found in the full version.} 

\begin{lemma}
\label{exp:expect}
Let $G$ be any $\epsilon$-expander with $\epsilon, \delta$ satisfying the conditions of Theorem~\ref{exp:phaseI}. Then for any 
time $t  \geq 0$, the cobra walk on $G$ with active set $S_t$ such that $|S_t| \leq \delta n$ satisfies $\E[|S_{t+1}|] \geq (1+\nu)|
S_t|$ for some constant $\nu > 0$. 
\end{lemma}
\onlyLong{
\begin{proof}
We will instead show that the portion of $N(S_t)$ not selected by the cobra walk is sufficiently small, $\E[|N(S_t) - S_{t+1}|] \leq |
N(S_t)| - (1+\nu)|S_t|$, and the result of the lemma will follow immediately. 

For each vertex $u \in N(S_t)$, define $X_u$ as an indicator random variable that takes value 1 if $u \notin S_{t+1}$ and 0 
otherwise.  Then $\prob{X_u = 1} = (1-1/d)^{k d_u}$, where $d_u$ is the number of neighbors $u$ has in $S_t$. Thus:
$$\E[|N(S_t) - S_{t+1}|] = \sum_{u \in N(S_t)} X_u = \sum_{u \in N(S_t)} (1 - \frac{1}{d})^{k d_u} \leq \sum_{u \in N(S_t)} e^{-\frac{k 
d_u}{d}}.$$ 
Because $\sum_{u \in N(S_t)} d_u  = d |S_t|$ and we are working with a convex function, we have that $\sum e^{-\frac{kd_u}{d}}
$ is maximized when all the values of $d_u$ are equal to either $1$ or $d$, with the exception of possibly one $d_u$ to act as 
the remainder. Let $R_1$ be the number of vertices in $N(S_t)$ where $d_u = 1$, and let $R_2$ be the number of vertices where 
$d_u = d$. We have the following system of equations:
\begin{eqnarray}
R_1 + R_2 &=& |N(S_t)| \\
R_1 + d R_2 &=& d |S_t| 
\end{eqnarray}
solving for $R_1$ and $R_2$, we get:
\begin{eqnarray}
R_1 &=& \dfrac{d}{d-1} (|N(S_t)| - |S_t|) \\
R_2 &=& \dfrac{1}{d-1} (d|S_t| - |N(S_t)|).
\end{eqnarray}
We now want to show that 
$$\E[|N(S_t) - S_{t+1}|] \leq R_1 e^{-\frac{k}{d}} + R_2 e^{-k}
				= \dfrac{d}{d-1}(|N(S_t)| - |S_t|) e^{-\frac{k}{d}} + \dfrac{1}{d-1} (d |S_t| - |N(S_t)|)e^{-k}$$ 
				$$\leq |N(S_t)| - (1+\nu)|S_t|.$$
Rearranging, we want to show that
\begin{eqnarray*}
 |N(S_t)|\left( 1 - \dfrac{d}{d-1} e^{-\frac{k}{d}} + \dfrac{1}{d-1} e^{-k} \right) +  |S_t| \left(\dfrac{d}{d-1} e^{-\frac{k}{d}} - \dfrac{d}{d-1} e^{-k} - 1 \right) \geq \nu |S_t|.
\end{eqnarray*}
We let $\alpha = \frac{1}{\epsilon^2 (1-\delta) + \delta}$, then $|N(S_t)| \geq \alpha |S_t|$  (by Theorem \ref{thm:tanner}) and we can divide through by $|S_t|$ in 
the expression immediately above. Since the first quantity in parenthesis is positive, and we don't care what $\nu$ is as long as 
it's a positive constant, we are down to needing:
$\alpha \left( 1 - \dfrac{d}{d-1} e^{-\frac{k}{d}} + \dfrac{1}{d-1} e^{-k} \right) + \left(\dfrac{d}{d-1} e^{-\frac{k}{d}} - \dfrac{d}{d-1} e^{-k} 
-1\right) > 0$.
Rearranging, we want
\begin{displaymath}
\label{exp:penult}
(\alpha - 1) \left(1 - \dfrac{d}{d-1} e^{-\dfrac{k}{d}} \right) - \dfrac{d-\alpha}{d -1} e^{-k} > 0.
\end{displaymath}
Taking the second-order Taylor approximation $e^{-\frac{k}{d}} \leq 1 - \frac{k}{d} + \frac{k^2}{2d^2}$, (\ref{exp:penult}) will be 
satisfied if 
\begin{displaymath}
(\alpha - 1) \left(1- \dfrac{d}{d-1} \left( 1 - \frac{k}{d} + \dfrac{k^2}{2d^2} \right) \right) - \dfrac{d - \alpha}{d -1} e^{-k} > 0
\end{displaymath}
which will be true for 
\begin{displaymath}
\frac{1}{\epsilon^2 (1 - \delta) + \delta} = \alpha > \frac{ d( d e^{-k} + (k-1)) - \frac{k^2}{2}}{d(e^{-k} + (k-1)) - \frac{k^2}{2}}  \\
\end{displaymath}
\end{proof}
}

%Note that these results will only hold for fairly strong expanders. It
%is known that the Ramanujan graphs have $\epsilon \leq 2\sqrt{d-1}/d$,
%which for suitable $d$ is more than enough to satisfy this bound.
%On the other hand, the $p$-cycle graph constructed form $\mathbb{Z}_m$, where each number $i$ is linked to $i+1$ and 
%$i-1$ and its multiplicative inverse mod $m$, though an expander, is too weak to meet the bound in ~\ref{exp:expect}. 

Next, we use a martingale argument to show that the number of vertices in $S_t$ is concentrated around its expectation. 
\onlyShort{The proof of Lemma ~\ref{exp:martingale} can also be found in the full version of the paper.}

\begin{lemma}
\label{exp:martingale}
For a cobra walk on a $d$-regular $\epsilon$-expander that satisfies the conditions in Lemma ~\ref{exp:expect}, at any time $t$ 
\begin{equation}
\prob{|S_{t+1}| - \E[|S_{t+1}|] \leq -\tau |S_t|} \leq e^{-\dfrac{\tau^2 |S_t|}{2k}} 
\end{equation}
\end{lemma} 

\onlyLong{
\begin{proof}
Arbitrarily index the the vertices of $S_t$,   $i =  \{1,\ldots, |S_t| = m\}$. Let $(Z_i^j)$ be a sequences of random variables ranging 
over the indices $i$ and  $j = \{ 1, \dots, k \}$, where $Z_i^j = v$ indicates the $i^{th}$ element of $S_t$ has chosen vertex $v$ to 
place it's $j^{th}$ pebble. Define $A$ as the random variable that represents the size of $S_{t+1}$. Then 
\begin{displaymath}
X^j_i = \E[A|Z^1_1,\ldots,Z_1^k,\ldots,Z_i^1,\ldots,Z_i^j]
\end{displaymath}
is the Doob martingale for $A$, with $X^k_m = |S_{t+1}|$. Since $X_i^j - X_i^{j-1} \leq 1$ and $X_{i}^1 - X_{i-1}^k \leq 1$ for all $i,j
$, Azuma's inequality yields:
\begin{equation}
\prob{|S_{t+1}| - \E[|S_{t+1}|] \leq -\tau |S_t|} \leq e^{-\frac{\tau^2 m^2}{2km}}  =  e^{- \frac{\tau^2 m}{2k}} 
\end{equation}
\end{proof} 
}

We now complete the proof of Lemma~\ref{exp:phaseI}. Using the bound of Lemma~\ref{exp:martingale} we show that 
with high probability we will cover at least $\delta n$ of the vertices of $G$ with a cobra walk  in logarithmic time by showing
 that the active set for some $t = O(\log n)$ is of size at least $\delta n$. 

The key to this proof is to view a cobra-walk on $G$ as a Markov
process over a state space consisting of all of the possible sizes of
the active set. In this interpretation, all configurations of pebbles
in a cobra-walk in which $i$ vertices are active are equivalent.  The
goal is to show that this new Markov process will reach a state
corresponding to an active set of size $\delta n$ quickly w.h.p. To
prove this, we first show that it is dominated by a restricted Markov
chain over the same state space in which any negative growth in the
size of the active set is replaced with a transition to the initial
state (in which only one vertex is active). We then in turn show that
the restricted walk is dominated by an even more restricted walk in
which the probability of negative growth is higher than in the first
restricted walk, bounded from below by a constant, and no longer
dependent on the size of the current state. We then show that the goal
of the lemma is achieved even in this walk by relating the process to
a negative binomial random variable.

\begin{proof}
We view a cobra-walk on $G$ as a random walk $W$ over the state space consisting of all of the possible sizes of the active set: 
$S(W) = \{1,\ldots,n\}$. We then define a Markov process $M_1$ that stochastically dominates $W$: Let $\tau = \nu/2$, where $
\nu$ is the expected growth factor of the active set as shown in Lemma~\ref{exp:expect}. The states of $M_1$, $S(M_1)$, are the 
same as $W$'s, but the transitions between states differ. Each $i \in S(W)$ can have out-arcs to many different states, but the 
corresponding $i \in S(M_1)$ has only two transitions. With probability $p_i = 1 - e^{-\frac{\nu^2 i}{8k}}$ transition to state $(1 + 
\nu/2)i$, and with probability $1-p_i$ transition to state $1$. Note that $p_i$ is derived from Lemma~\ref{exp:martingale}.

In $M_1$, each transition probability is still a function of the current state $i$, and as mentioned above we would like to 
eliminate this dependence. Thus, define $M_2$ as a random walk over the same state space. However, we will deal only with a 
subset of $S(M_2)$: the states: $(1+\nu/2)^i C$ for $i \in \mathbb{Z}$ and a suitably large constant $C$. We then have the 
following transitions for each state in the chain (which will begin once it hits $C$). Setting $r = \nu^2/8k$, at state $(1+\nu/2)^i C:
$ 1) Transition to state $(1+\nu/2)^{i+1}C$ with probability $p'_i  = 1 - e^{-r C (1 + \frac{i \nu}{2})}$. 2) Transition to state $C$ with 
probability $1-p'_i$. This Markov chain oscillates between  failure (going to $C$) and growing by a factor of $1+\nu/2$. Note that 
to get success (i.e., reaching a state of at least $\delta n$), we need $\Omega(\log n)$ growing transitions.   

The probability that in a walk on this state space that we ``fail" and go back to $C$ before hitting $\delta n$ is bounded by $1/2$, 
since  $\sum_{i=0}^{\infty} e^{-rC(1+i\frac{\nu}{2})} \leq e^{-rC} \sum_{i=0}^{\infty} e^{i rC \frac{\nu}{2}} = \frac{e^{-rC}}{1 - e^{-rC
\frac{\nu}{2}}} \leq \frac{1}{2}$, provided that $C$ is sufficiently large as a function of $r$ (which is itself only a function of the 
branching factor and the constant $\nu$). 

Consider each block of steps that end in a failure (meaning we return to $C$).  Then clearly w.h.p. after $b \log n$ trials, for 
some constant $b$, we will have a trial that ends in success (i.e., reaching an active set of size $\delta n$ vertices). In these $b 
\log n$ trials, there are exactly that many returns to $C$. However, looking across all trials that end in failure, there are also only 
a total of $O(\log n)$ steps that are successful (i.e.,  involve a growth rather than shrinkage). To see why this is true, note that the 
probability of a failure after a string of growth steps goes down supralinearly with each step, so that if we know we are in a failing 
trial it is very likely that we fail after only a few steps. Thus, there cannot be too many successes before each failure. Indeed, the 
probability that we fail at step $i$ within a trial can be bounded. Thus, $\prob{\text{Failure at step } i  | \text{ eventual failure}}$

\begin{eqnarray*}
 &=&  \frac{\prob{\text{Failure at step i}}}{\prob{\text{Eventual failure}}} \\
 &=& \frac{ e^{-rC(1 + i \nu /2) }}{\sum_{i=1}^{\infty} \left(\prod_{j=1}^{l-1} (1 - e^{-rC(1+j \nu/2)}\right) e^{-rC(1+l \nu/2)}} \\
 &\geq& \frac{1}{ \sum_{i=1}^{\infty} e^{- i r C \nu/2}} \geq 1 - e^{-rC\nu/2}
\end{eqnarray*}
and thus the probability of advancing is no more than \text{ } $e^{-r C \nu /2}$, also a quantity that does not depend on $i$.  This 
is a negative binomial random variable with distribution $w(k,p)$, the number of coin flips needed to obtain $k$ heads with 
heads probability $p$. Identifying heads with a failure (i.e. returning to $C$) and tails with making a growth transition, we have a 
random variable $w(k,p)$, the number of coin flips needed for $k$ failures with probability of failure $p  = 1 - e^{-r C \nu / 2}$. It is 
well known that $\prob{w(k,p) \leq m} = \prob{B(m,p) \geq  k}$, where $B(m,p)$ is the binomial random variable counting the 
number of heads within $m$ $p$-biased coin flips. Thus, $\prob{w(k,p) > m}=  \prob{B(m,p) < k}$. Setting $k = a \log n$ and $m 
= b \log n$,  we have, $\prob{B(m,p) \leq \E[B(m,p)] - t} = \prob{B(m,p) < pm -t}  \leq e^{\frac{-2 t^2}{m}}$. 
We let $k=pm-t$, and solving for $t$ we get $t = (pb -a) \log n$. This gives us 
$$\prob{B(m,p) < k)} \leq \frac{1}{n^{\frac{(pb - a)^2}{b}}},$$ establishing that there are at most $O(\log n)$ successes 
within  $O(\log n)$ trials ending in failure. Via stochastic dominance this bound holds for our original cobra walk process.

\end{proof} 

\subsection{Phase 2} 


Once the active set has reached size $\Omega(n)$, we need a different
method to show that the cobra-walk achieves full coverage in  $O(\log^2
n)$ time.  We can not simply pick a random pebble and restart the
cobra-walk from this point $O(\log n)$ times because we know nothing
about the distribution of the $\delta n$ pebbles after restart, and
the restarting method would require the pebbles to be i.i.d. uniformly
across the vertices of $G$.  As a result, we are unable to establish a
straightforward bound on $h_{max}$ and invoke Matthew's Theorem.

Hence, to prove Lemma~\ref{exp:phaseII} we develop a different
process, which we will call $W_{alt}$, which stochastically dominates
the cobra walk. In $W_{alt}$, no more branching or coalescing occurs,
and we also modify the transition probabilities of the pebbles on a
vertex-by-vertex basis, depending on the number of pebbles at a
vertex.  For technical reasons, we also make the $W_{alt}$ process
lazy in that in any given round, with probability $1/2$, the pebbles
all remain in the same location.

\begin{definition}
For any time $t$ and any collection of $S$ pebbles on $V$ (there can
be more than 1 pebble at a vertex), define \textbf{ $W_{alt}(t+1)$ }
as follows.  With probability 1/2, all the pebbles remain in the same
location; with probability 1/2, the pebbles move as follows.  Let $A
\subseteq V$ be the set of all vertices with 1 pebble at time $t$. Let
$B \subseteq V$ be the set of all vertices with exactly 2 pebbles, and
let $C$ be the set of all vertices with more than 2 pebbles. Then, (a)
for every $v \in A$, the pebble at $v$ uniformly at random selects a
vertex in $\Gamma(v)$ (the neighborhood of $v$ not including itself)
and moves to it; (b) for every $v \in B$, each pebble at $v$ uniformly
at random selects a vertex in $\Gamma(v)$ and moves to it; (c) for
every $v \in C$, arbitrarily index the pebbles at v. Then the first
two pebbles each (index $1,2$) then pick a neighbor $\in \Gamma(v)$ to
move to, uniformly at random. Let $u,w$ be the two neighbors picked by
pebbles $1,2$. (Note that $w=u$ is a possible outcome. The remaining
pebbles (those with index $>2$), still in the same time step, each
independently pick $u$ or $w$ with probability $1/2$ and move to the
vertex they have selected.
\end{definition} 

The process $W_{alt}$ can be thought of as a kind of coalescing (lazy)
random walk in which the threshold for coalescence is three pebbles on
a vertex rather than the standard two, with the added condition that
the third (and higher) token chooses which of the first two tokens to
coalesce with by flipping an unbiased coin.

Furthermore, at any time $t$, when $W_{alt}$ is not lazy, a vertex
with two or more pebbles behaves locally exactly the same in $W_{alt}$
and a cobra walk. The divergence in behavior occurs only for those
vertices with one pebble. In $W_{alt}$ they behave like vertices
participating in a simple lazy random walk (or like vertices in a
cobra walk in which both pebbles have chosen the same neighbor to move
to in the next round. In light of these modifications, the active set
of $W_{alt}$ at any time $t$ can be viewed as a (possibly proper)
subset of the active set of a cobra walk on $G$ at an earlier time
that accounts for the lazy steps of $W_{alt}$, if both are started
from identical initial conditions (i.e. distribution of
pebbles). Therefore, the probability that the cover time of $W_{alt}$
is greater than some value $x$ is at least the probability of the
cover time of the cobra walk being greater than $x$. Thus, the cover
time of $W_{alt}$ stochastically dominates the cover time of a cobra
walk when started from the same initial condition.

Thus if we can prove that the cover time of $W_{alt}$ on $G$ is
$O(\log n)$ with high probability, this will imply that the cover time
of the cobra walk on $G$ has the same upper bound as well.

\junk{
If at time $t$ a vertex during process $W_{alt}$ has two or more pebbles, at each time step it behaves identically to a vertex
running a cobra walk. On the other hand, if there is only one pebble at vertex running $W_{alt}$ it acts like a simple random walk. 
Thus the number of active vertices at the next time step in $W_{alt}$ is a (possibly proper) subset of the vertices with pebbles if the 
graph were running the cobra walk instead. Since this will be true at every time step, $W_{alt}$ stochastically dominates the 
cobra walk w.r.t cover time $\tau$ of $G$, and it will be sufficient to prove the following:}
\begin{lemma}
\label{exp:fullcoverage}
Let G be a bounded-degree $d$-regular $\epsilon$ -expander graph, with
$\epsilon$ sufficiently small to satisfy the conditions in
Lemma~\ref{exp:expect}. Let there be $\delta n$ pebbles distributed
arbitrarily over $V$, with at most one pebble per vertex, for a
constant $\delta < 1/2$.  \junk{Let $\alpha_2$ be the second-largest
  eigenvalue of the adjacency matrix of $G$. From our $
  \epsilon$-expander definition, $\alpha_2 \leq \epsilon d$. For every
  $\epsilon$, there exists constant $\beta$ that is the edge expansion
  constant of $\Gtensor$ (defined below).  Furthermore, let $s =
  \dfrac{88(d+1)^2}{\beta^2} \log n$. }  Starting from this
configuration, the cover time of $W_{alt}$ on $G$ is $O(\log^2 n)$,
with high probability.
\end{lemma}
\begin{proof}
Our proof relies on showing that each vertex in $G$ has a constant
probability of being visited by at least one pebble during an epoch of
$W_{alt}$ lasting $\Theta(\log n)$ time. Once this has been
established, all vertices of $G$ will be covered w.h.p. after $O(\log
n)$ epochs lasting $\Theta(\log n)$ steps each.

Define $E_i$ to be the event that pebble $i$ covers an arbitrary
vertex $v$ at time $s = \Theta(\log n)$, where the constant hidden in
the $\Theta$ notation is chosen below to be sufficiently large. We
want to prove that the probability that $v$ is covered by at least one
pebble, $\prob{\bigcup_i E_i}$, is constant.  For pebbles $i$ and $j$,
we cannot assume that $E_i$ and $E_j$ are independent, since the
transition probabilities of the walks of $i$ and $j$ will not be
independent if they are spatially and temporally co-located.  However,
we can calculate an upper bound using a second-order
inclusion-exclusion approximation:
\begin{equation*}
\prob{\bigcup_i E_i}
\geq \sum_i \prob{E_i} - \frac{1}{2}\sum_{i \neq j} \prob{E_i \cap E_j}
\end{equation*}
As a marginal probability, $\prob{E_i}$ can be viewed as the
probability that the (simple) random walk of pebble $i$ hits $v$ at
time $s$.  This is justified because if we only observe the movement
of pebble $i$, at any time $t$, if $i$ is at vertex $w$, its
probability of walking to each of $w$'s $d$ neighbors is $1/2d$,
regardless of whether it is the first, second, or third pebble at $w$.
Since it reduces to analyzing a simple random walk, we only need to
look at the elements of $z A^s$, where $A$ is the stochastic
transition matrix of the simple lazy random walk on $G$ and $z$ is a
vector with $z(l)$ equal to $1$ for $l$ equal to the position of pebble $i$
at the beginning of the epoch, and $0$ in all other positions.  By a
standard analysis (e.g., see~\cite[Lemma~4.8]{AAKKLT}) it follows that
each coordinate of $A^{s} z$ differs from $1/n$ by at most
$\frac{1}{2n}$ for $s \ge c\log n$, where $c$ is a sufficiently large
constant.  Thus $\prob{E_i} \geq \frac{1}{2n}$.

Next we establish an upper bound for $\prob{E_j \cap E_i}$, the joint
(and hence non-independent) walks of pebbles $i$ and $j$. For the
purposes of this analysis, we will consider pebble $i$ to be the
higher-priority pebble: that is, if at any time $i$ and $j$ are
co-located at some vertex and the process is not lazy in that round,
we assume that $i$ has first priority and chooses a neighbor to move
to in the next step independently with uniform probability. We assume
that $j$ has third or lower priority, and will choose $i$'s
destination with probability $1/2$ and thus with probability $1/2$
choose a neighbor uniformly at random.  We can view the walks of $i,j$
as a random walk on the tensor product $\Gtensor$. The tensor product
has vertex set that is the Cartesian product $V(G) \times
V(G)$. Vertex $(u,u')$ of $\Gtensor$ has an edge to $(v,v')$ if and
only $(u,v)$ and $(u',v')$ are edges of $G$.  Note that the joint walk
of $i,j$ on $G$ does not map to a simple random walk on $\Gtensor$ --
rather, it maps to a walk on a directed graph formed from $\Gtensor$
with weights chosen appropriately based on the process $W_{alt}$. In
Lemma~\ref{directedmarkov} we show that this walk, viewed as a
non-reversible, irreducible Markov chain, has a stationary
distribution close to $1/n^2$, that it converges rapidly to the
stationary distribution, and thus after $s$ steps, the probability
that $i$ and $j$ are at the same vertex in $G$ is no more than $2/(n^2
+ n) + 1/n^4$.

With this result, we then have:
\begin{eqnarray*}
\prob{\bigcup E_i }
 &\geq& \sum_i \prob{E_i} - \frac{1}{2} \sum_{i \neq j} \prob{E_j \cap E_i } \\
&\geq& \delta n \frac{1}{2n} - \binom{\delta n}{2}\left( \frac{2}{n^2 + n}  + \frac{1}{n^4}\right) \\
&\geq& \frac{\delta}{2} - \frac{\delta}{2} (\delta n^2 - n)  \left( \frac{2}{n^2 + n}  + \frac{1}{n^4}\right) \\
&\geq& \frac{\delta}{2} - \frac{\delta^2 n^2}{n^2 + n}  - \frac{\delta^2}{n^2} \\
&\geq& \frac{\delta}{2} - \delta^2,
\end{eqnarray*}
which is a positive constant for any $\delta < 1/2$. The last
inequality holds because the term $n^2/(n^2 + n) + 1/n^2$ is at most
$1$ for $n \ge 2$.
\end{proof}


\begin{lemma}
\label{directedmarkov} 
Let $G$ and $s$ be defined as in Theorem~\ref{exp:fullcoverage}. Let $i$ and $j$ be two pebbles walking on $G$ according to the rules of $W_{alt}$. If $E_i \cap E_j$ defined as the event in which $i$ and $j$ are both at arbitrary vertex $v \in G$ at time $s$, then $\prob{E_i \cap E_j} \leq 1/n^2$. 
\end{lemma}
\begin{proof}
Let $\Gtensor$ be the tensor product chain defined as above.  We first
make some observations about the structure of this graph. We note that
there are two types of vertices of $\Gtensor$. The first type involves
all vertices that have the form $(u,u)$, where $u\in V(G)$.  A pebble
at $(u,u)$ would correspond to two pebbles occupying $u$ in the paired
walk of $i,j$ on $G$. We label this set $S_1$. The cardinality of
$S_1$ is $n$. The remaining vertices, which we place in the set $S_2$,
are of the form $(u,v)$ for $u \neq v$. There are $n^2 - n$ such
vertices Also note that in the undirected graph $\Gtensor$, each
vertex has degree $d^2$. Further, every vertex in $S_1$ will have $d$
neighbors also in $S_1$, by virtue of $G$ being $d$-regular.

Many of the spectral properties of $G$ apply to $\Gtensor$ as
well. Primarily, because $G$ is an $\epsilon$-expander, the transition
matrix of a simple random walk on $G$ has a constant second eigenvalue
$\alpha_2(G)$ bounded away from $0$. It is well known
(c.f.~\cite{LevinPeresWilmer2006}) that $\Gtensor$ will have $\alpha_2
(\Gtensor) = \alpha_2(G)$, which will will refer to as $\alpha_2$
henceforth.

We now take the undirected graph $\Gtensor$ and transform it into a
directed graph $D(\Gtensor)$ as follows. For every undirected edge
$(x,y)$ in $\Gtensor$, replace it with 2 directed edges: $x
\rightarrow y$ and $y \rightarrow x$. As mentioned, every vertex in
$S_1$ will have $d$ neighbors also in $S_1$, meaning there will be one
directed arc $x \rightarrow y$ for every vertex $x \in S_1$ and $y \in
N(x), y \in S_1$. We now add an additional $d$ copies of edge $x
\rightarrow y$ for every such original edge.  Finally, to account for
the fact that $W_{alt}$ is a process in which all pebbles stay
simultaneously at their respective locations with probability $1/2$,
we add as many self-loops at each vertex of $D(\Gtensor)$ as the
number of outgoing edges at the vertex.

It is relevant for our analysis to note that because of the regularity
of the subgraph of $\Gtensor$ induced on $S_1$, for every vertex in
$D(\Gtensor)$, the number of out-edges will equal the number of
in-edges, and hence $D(\Gtensor)$ is an Eulerian digraph.
Furthermore, we can now calculate the transition probabilities of a
random walk on $D(\Gtensor)$ where an outgoing edge from vertex $x$ is
picked with probability equal to the reciprocal of its out-degree.
For all vertices in $S_2$, the probability that the walk stays at the
vertex is $1/2$; every other transition occurs with probability
$1/(2d^2)$. This includes edges from $S_2$ into $S_1$. On the other
hand, while the probability that the walk stays at a vertex in $S_1$
is $1/2$, the probabilities of transitions from a vertex in $S_1$ to
any other vertex is modified: The probability of transitioning from a
vertex $x \in S_1$ to one of its $d^2 -d$ neighbors in $S_2$ is now
$1/(4d^2)$, while the probability of transitioning to a neighbor in
$S_1$ has become $(d+1)/(4d^2)$ on account of the multiple edges. We
have thus constructed a walk on digraph $D(\Gtensor)$ that maps
exactly to the joint walk of pebbles $i,j$ on $G$ according to the
rules of $W_{alt}$.

Because the walk on $D(\Gtensor)$ is irreducible, it has a stationary
distribution $\pi$, which is the (normalized) eigenvector of the
dominant eigenvalue of the transition matrix $M$ of the walk on
$D(\Gtensor)$. Furthermore, because $D(\Gtensor)$ is Eulerian, the
stationary distribution of vertex $x$ is exactly given by: $d^+(x)/m$,
where $m$ is the number of edges. Therefore there are only two
distinct values of the components of the stationary vector: for all $x
\in S_1$, $\pi(x) = 2/(n^2 + n)$, while for all $y \in S_2$, $\pi(y)=
1/(n^2 + n)$.

Because $G$ and hence $\Gtensor$ have such nice spectral properties,
and because $D(\Gtensor)$ represents a minor modification of
$\Gtensor$, it would be reasonable to intuit that $D(\Gtensor)$ also
has some of the same properties. Yet, one must proceed with caution
when analyzing Markov chains on directed graphs, as some properties
that hold for chains on undirected graphs do not carry
through. However, following closely the work
of~\cite{Chung05laplaciansand} we can verify that the random walk on
$D(\Gtensor)$ converges rapidly to its stationary distribution.

For succinctness of notation denote $\D = D(\Gtensor)$. Consider the
function $F_{\pi}: E(\D) \rightarrow \Re$ given by $F_{\pi}(x,y) =
\pi(x) P(x,y)$, where $\pi(x)$ is the $x$-th component of the
stationary distribution of the walk on $\D$ and $P(x,y)$ is the
associated transition probability moving from $x$ to $y$. Then
$F_{\pi}$ is the \textbf{circulation} associated with the stationary
vector as shown in Lemma 3.1 of ~\cite{Chung05laplaciansand}. Note
that a circulation is any such function that satisfies a balance
equation: $\sum_{u, u\rightarrow v} F(u,v) = \sum_{w,v\rightarrow w}
F(v,w)$.

There is a Cheeger constant for every directed graph, defined as:
\begin{equation}
h(G) = \inf_S \frac{F_{\pi}(\partial S)}{\min\{F_{\pi}(S),F_{\pi}(\bar{S})\}}
\end{equation}
where $F_{\pi}(\partial S) = \sum_{u\in S,v\notin S} F(u,v)$, $F(v) =
\sum_{u,u\rightarrow v} F(u,v)$ and $F(S) = \sum_{v \in S} F(v)$ for a
set S. Furthermore, Theorem 5.1 of~\cite{Chung05laplaciansand} shows
that the second eigenvalue, $\lambda$, of the Laplacian of $\D$
satisfies:
\begin{equation}
2 h(\D) \geq \lambda \geq \frac{h^2(\D)}{2}
\end{equation}
The Laplacian of a directed graph is defined slightly differently than for an undirected graph. However, because we will not use the Laplacian directly in our analysis, we refer the reader~\cite{Chung05laplaciansand} for the definition. We will directly bound the Cheeger constant for $\D$, and hence produce a bound on the second eigenvalue of the Laplacian. This second bound will then be used to provide a bound on the convergence of the chain to its stationary distribution (see Theorem~\ref{thm-laplacian} below). 

First, w.l.o.g., assume that $F_{\pi}(S)$ is smaller than its
complement.  Furthermore assume that $S$ is the set that satisfies the
$\inf$ condition in the Cheeger constant. We have $F_{\pi}(\partial S)
= \sum_{x \rightarrow y, x \in S, y \in \bar{S}} \pi(x) P(x,y)$, and
$F_{\pi}(S) = \sum_{x \rightarrow y, x \in S} \pi(x) P(x,y)$. The
first sum occurs over all (directed) edges that cross the cut of
$S$. Fortunately, we are already able to provide a lower bound on the
size of this cut. Observing that $\D$ has at least as many edges
crossing the cut as a cut on the equivalent set $S$ in $\Gtensor$, and
recalling that $\Gtensor$ has second eigenvalue $\alpha_2$, we can
appeal to $\alpha_2$ being bounded away from zero by a constant (by
virtue of $G$'s expansion, recall) to state that there exists some
constant $\beta$ (depending on $\alpha_2$) such that there are at
least $\beta |S|$ edges crossing the cut. We can thus provide a lower
bound for the entire Cheeger constant: \junk{\begin{eqnarray*} h(\D)
    &=& \inf_S \frac{F_{\pi}(\partial
      S)}{\min\{F_{\pi}(S),F_{\pi}(\bar{S})\}} \\ &\geq& \dfrac{\beta
      |S| P_{min} \pi_{min}}{|S| P_{max} \pi_{max}} \\ &=& \beta \cdot
    \dfrac{\dfrac{1}{2d^2} \dfrac{1}{(n^2 + n)}}{\dfrac{d+1}{2d^2}
      \dfrac{2}{(n^2 + n)}} = \dfrac{\beta}{2(d+1)}
\end{eqnarray*}  }
\begin{eqnarray*}
h(\D) &=& \inf_S \frac{F_{\pi}(\partial S)}{\min\{F_{\pi}(S),F_{\pi}(\bar{S})\}} \\
&\geq& \dfrac{\beta |S| P_{min} \pi_{min}}{|S| P_{max} \pi_{max}} \\
&=& \beta \cdot \dfrac{\dfrac{1}{4d^2} \dfrac{1}{(n^2 + n)}}{\dfrac{1}{2} \dfrac{2}{(n^2 + n)}} =  \dfrac{\beta}{4d^2}  
\end{eqnarray*}  

We can then apply the lower Cheeger inequality to have $\lambda \geq
\dfrac{\beta^2}{32 d^4}$.  We now show the rapid convergence (in
logarithmic time) of the walk on $\D$ to the stationary
distribution. To measure distance from the stationary distribution, we
use the $\chi-$\textit{square-distance}:
\begin{equation}
\Delta'(t) = \max_{y \in V(\D)} \left( \sum_{x \in V(G)} \dfrac{(P^t(y,x) - \pi(x))^2}{\pi(x)}\right)^{1/2}
\end{equation} 

It can be shown that a rapid convergence for $\Delta'$ implies a rapid convergence for the total variational distance, and thus the distribution of a random walk starting anywhere in $\D$ will be close to its stationary distribution for every vertex. 

We next apply Theorem 7.3 from~\cite{Chung05laplaciansand} which we state here for clarity: 
\begin{theorem} 
\label{thm-laplacian}
Suppose a strongly connected directed graph $G$ on $n$ vertices has Laplacian eigenvalues $0=\lambda_0 \leq \lambda_1 \leq \ldots \leq \lambda_{n-1}$. Then G has a lazy random walk with the rate of convergence of order $2 \lambda_1^{-1} (-\log \min_x \pi(x))$. Namely, after at most  $t \geq 2 \lambda_1^{-1}((-\log \min_x \pi(x) + 2c)$  steps, we have: 
\begin{equation*}
\Delta'(t) \leq e^{-c}
\end{equation*}
\end{theorem} 

Recall that we provided a constant lower bound for $\lambda$, the second-smallest eigenvalue of the Laplacian of $\D$. Hence we can apply it to the minimum running time of the random walk on $\D$ to show that after at most: 
\begin{equation*}
s = \dfrac{32 d^4}{\beta^2} \left(\log(n^2 + n) + 4 \log n^2 \right) 
\end{equation*}
steps we will have $\Delta'(t) \leq \dfrac{1}{n^4}$ Therefore, for the
random walk on $\D$, after a logarithmic number of steps $s$ (in $n$,
the size of $G$), a walk that starts at any initial distribution on
$V(\D)$ will be within $1/n^{-4}$ of the stationary distribution of
any vertex. Mapping our analysis back directly to the coupled walk of
$i,j$ on $G$, $\prob{E_i \cap E_j} \leq 2/(n^2 + n) + 1/n^4$ when
pebbles $i$ and $j$ start from any initial position.
\end{proof}

 
